import java.util.LinkedList;
import java.util.Queue;

public class LeetCode116 {

    public static void main(String[] args) {

    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    public Node connect(Node root) {
        if (root == null){
            return root;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);

        while (!queue.isEmpty()){
            int size = queue.size();

            for (int i = 0; i < size; i++){
                Node node = queue.poll();


            }
        }

        return null;
    }

    /**
     * 1.临时保存当层的最左侧的节点
     * 2.临时保存当前位置的父节点
     * 3.保存下一层最左侧节点
     *
     * 如果当前节点是左节点，则next节点是当前节点的父节点的右节点
     * 如果当前节点是右节点，则next节点是当前父节点的next节点的左节点
     * 如果当前父节点的next节点为空，则表示当前层已经遍历完成
     *
     * @param root
     * @return
     */
    public Node connect1(Node root){

        if (root != null){

            Node lastLayer = root;
            while (lastLayer.left != null){
                Node head = lastLayer;

                while (head != null){
                    head.left.next = head.right;

                    if (head.next != null){
                        head.right.next = head.next.left;
                    }
                    head = head.next;
                }
                lastLayer = lastLayer.left;
            }
        }

        return root;
    }



}
